#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include "tree.h"

using namespace std;

void getMaxPathHelper(Tree *root, int rootSum, int &maxPathSum, int &maxSum)
{
    if (!root) {
	maxPathSum = 0;
	return;
    }

    int leftLeftSum = 0, leftRightSum = 0, rightLeftSum = 0, rightRightSum = 0, maxLeftSum = 0, maxRightSum = 0;
    getMaxPathHelper(root->left, rootSum + root->data, maxLeftSum, maxSum);
    getMaxPathHelper(root->right, rootSum + root->data, maxRightSum, maxSum);
    
    if (maxSum < rootSum + root->data + maxLeftSum + maxRightSum) {
	cout << root->data << " " << maxLeftSum << " " << maxRightSum << endl;
        maxSum = rootSum + root->data + maxLeftSum + maxRightSum;
    }
    maxPathSum = root->data + max(maxLeftSum, maxRightSum);
    return;
}

int getMaxPath(Tree *root)
{
    int rootSum = 0;
    int leftSum = 0;
    int rightSum = 0;
    int maxSum = 0;
    int ans = 0;
    int maxPathSum = 0;
    getMaxPathHelper(root, rootSum, maxPathSum, maxSum);
    return maxSum;
}

int main(int argc, char **argv)
{
    int input[] = {21,7,5,6,3,2,1,4,6,23,43,54,12,54,8,10,11,35,56};
    //int input[] = {7};
    Tree *root = NULL, *root2 = NULL;
    int result;

    for (int i = 0; i < sizeof(input)/sizeof(int); i++) {
        TreeInsert(root, input[i]);
    }

    print_ascii_tree(root);

    result = getMaxPath(root);
    cout <<"Max Path of the tree is " << result << endl;
}
